package zw_901_1000.zw_905_按奇偶排序数组;

class Solution {

    public static void main(String[] args) {
        int[] nums = {3, 1, 2, 4};
        int[] parity = sortArrayByParity(nums);
        for (int i : parity) {
            System.out.print(i + " ");
        }

    }

    /**
     * 双指针
     *
     * @param nums
     * @return
     */
//    public int[] sortArrayByParity(int[] nums) {
//        int n = nums.length;
//        int[] res = new int[n];
//        int left = 0, right = n - 1;
//        for (int num : nums) {
//            if (num % 2 == 0) {
//                res[left++] = num;
//            } else {
//                res[right--] = num;
//            }
//        }
//        return res;
//    }


    /**
     * 原地交换
     *
     * @param nums
     * @return
     */
    public static int[] sortArrayByParity(int[] nums) {
        int left = 0, right = nums.length - 1;
        while (left < right) {
            while (left < right && nums[left] % 2 == 0) {
                left++;
            }
            while (left < right && nums[right] % 2 == 1) {
                right--;
            }
            if (left < right) {
                int temp = nums[left];
                nums[left] = nums[right];
                nums[right] = temp;
                left++;
                right--;
            }
        }
        return nums;
    }


}
